JOI 08予選 E おせんべい(難易度6)
まず, $ Rの制約が小さいことに注目しよう.
2回以上裏返しても意味がないので, ここで各行について裏返すか裏返さないかbit全探索することを考える.
さて, bit全探索したあとどのように$ 0の個数を最大化すればよいだろうか？ これは貪欲法でできる.
各列について, $ 0が$ 1より少なければ裏返した方が得である(すでに行の裏返し方は決まっているのでこれ以上変化することはない).
よってこの問題が$ O(2^RC)で解けた.
詳しい実装は自分の提出を見ていただきたい(XOR演算を用いて裏返しをしていることなど, 高度な実装方法が含まれることに注意).